public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] nums = new int[] {1,1,1,1,1};
        System.out.println(test.findTargetSumWays(nums, 3));
    }

    public int findTargetSumWays(int[] nums, int target) {
        /**
         * 目标和
         * 状态表示：
         *  dp[i][j]表示在以i下标为结尾的所有元素中选择，使其总和等于j，此时的组合数目
         * 状态转移方程：
         *
         * 初始化：
         *  使用虚拟位置法，对第一行第一列
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  dp[n][target];
         * */
        // 1 预处理
        int n = nums.length;
        int total = 0;
        for(int x: nums) {
            total += x;
        }
        int t = (total + target) / 2;
        // -边界情况处理
        if(t < 0 || (total + target) % 2 == 1) {
            return 0;
        }
        // 2 创建dp表
        int[][] dp = new int[n+1][t+1];
        // 3 初始化
        dp[0][0] = 1;
        // 4 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= t; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]) {
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }
        // -打印查看
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= t; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("=========");
        // 5 返回值
        return dp[n][t];
    }
}
